/*
 * StringMatchingOnOrderedAlphabets.cpp
 *
 *  Created on: 03-09-2013
 *      Author: Krzychu
 */

#include "StringMatchingOnOrderedAlphabets.h"

#include "../Structures/Config.h"

#include <stdio.h>
#include <string.h>

#define MAX(a, b) (a > b) ? a : b
#define MIN(a, b) (a < b) ? a : b

StringMatchingOnOrderedAlphabets::StringMatchingOnOrderedAlphabets()
{

}

StringMatchingOnOrderedAlphabets::~StringMatchingOnOrderedAlphabets()
{

}

std::string StringMatchingOnOrderedAlphabets::getName()
{
	return "SMOA";
}

void StringMatchingOnOrderedAlphabets::nextMaximalSuffix(char *x, int m,
        int *i, int *j, int *k, int *p)
{
	char a, b;

	while (*j + *k < m)
	{
		a = x[*i + *k];
		b = x[*j + *k];
		if (a == b)
		{
			if (*k == *p)
			{
				(*j) += *p;
				*k = 1;
			}
			else
			{
				++(*k);
			}
		}
		else if (a > b)
		{
			(*j) += *k;
			*k = 1;
			*p = *j - *i;
		}
		else
		{
			*i = *j;
			++(*j);
			*k = *p = 1;
		}
	}
}

searchResult StringMatchingOnOrderedAlphabets::execute(std::string text,
		std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	char* textChar = (char*) text.c_str();

	int i, ip, j, jp, k, p;

	/* Searching */
	ip = -1;
	i = j = jp = 0;
	k = p = 1;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

 		while (i + j < textSize && i < patternSize && pattern[i] == text[i + j])
		{
			++i;
		}
		if (i == 0)
		{
			++j;
			ip = -1;
			jp = 0;
			k = p = 1;
		}
		else
		{
			if (i >= patternSize)
			{
				result.positionsFound.push_back(j);
				if (Config::getInstance()->getFindOneOccurence())
				{
					return result;
				}
			}
			nextMaximalSuffix(textChar + j, i + 1, &ip, &jp, &k, &p);
			if (ip < 0 ||
					(ip < p &&
					memcmp(textChar + j, textChar + j + p, ip + 1) == 0))
			{
				j += p;
				i -= p;
				if (i < 0)
				{
					i = 0;
				}
				if (jp - ip > p)
				{
					jp -= p;
				}
				else
				{
					ip = -1;
					jp = 0;
					k = p = 1;
				}
			}
			else
			{
				int min = MIN(i - ip - 1, jp + 1);

				j += MAX(ip + 1, min) + 1;
				i = jp = 0;
				ip = -1;
				k = p = 1;
			}
		}
	}

	return result;
}

